package leetcode.weekly.week342;

import java.util.TreeMap;

//Solution3Test
public class Solution3 {
	public int[] getSubarrayBeauty(int[] nums, int k, int x) {

		Record record = new Record(100);
		int[] ans = new int[nums.length - k + 1];
		for (int i = 0, j = 0; i < nums.length; i++) {
			int num = nums[i] + 51;// 0,50,100
			record.add(num);
			if (i >= k) {
				record.sub(nums[i - k] + 51);
			}
			if (i >= k - 1) {
				ans[j++] = f(record, x);
			}
		}
		return ans;

	}

	private int f(Record record, int x) {
		int l = 0, r = 101;
		int ans = -1;
		while (l < r) {
			int m = (r + l) / 2;
			int s = record.query(m);
			if (s >= x) {
				r = m;
			} else {
				l = m + 1;
			}
		}
		return l < 51 ? l - 51: 0;
	}

	class Record {
		int len;
		int[] arr;

		public Record(int n) {
			len = n + 2;
			arr = new int[len];
		}

		public void add(int num) {
			while (num < len) {
				arr[num]++;
				num += this.lowbit(num);
			}
		}

		public void sub(int num) {
			while (num < len) {
				arr[num]--;
				num += this.lowbit(num);
			}
		}

		public int query(int num) {
			int ans = 0;
			while (num > 0) {
				ans += arr[num];
				num -= this.lowbit(num);
			}
			return ans;
		}

		public int lowbit(int num) {
			return num & -num;
		}
	}

}
